package suanfa;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class findOrder {
    public int[] findOrder(int n, int[][] prerequisites) {
        List<List<Integer>> edges=new ArrayList<>();
        for(int i=0;i<n;i++){
            edges.add(new ArrayList<>());
        }
        int[] in=new int[n];
        for(int i=0;i<prerequisites.length;i++){
            int a=prerequisites[i][0],b=prerequisites[i][1];
            edges.get(b).add(a);
            in[a]++;
        }
        Queue<Integer> q=new LinkedList<>();
        int index=0;
        int[] ret=new int[n];
        for(int  i=0;i<n;i++){
            if(in[i]==0) q.add(i);
        }
        while(!q.isEmpty()){
            int t=q.poll();
            ret[index++]=t;
            for(int a:edges.get(t)){
                in[a]--;
                if(in[a]==0) q.add(a);
            }
        }
        if(index==n) return ret;
        else return new int[0];
    }
}

